package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class Q153 {

	/**
	 * @param num:    Given the candidate numbers
	 * @param target: Given the target number
	 * @return: All the combinations that sum to target
	 */
	List<List<Integer>> rs = new ArrayList<>();

	public List<List<Integer>> combinationSum2(int[] num, int target) {
		// write your code here
		if (num == null || num.length == 0) {
			return rs;
		}
		boolean[] used = new boolean[num.length];
		int sum = 0;
		Arrays.sort(num);
		search(0, num, sum, used, target);
		return rs;
	}

	private void search(int i, int[] num, int sum, boolean[] used, int target) {
		// TODO Auto-generated method stub
		if (sum == target) {
			save(num, used);
			return;
		}
		if (sum > target) {
			return;
		}
		for (int j = i; j < num.length; j++) {
			if (!used[j]) {
				if (j > 0 && num[j] == num[j - 1] && !used[j - 1]) {
					continue;
				}
				used[j] = true;
				sum = sum + num[j];
				search(j + 1, num, sum, used, target);
				sum = sum - num[j];
				used[j] = false;
			}

		}
	}

	private void save(int[] num, boolean[] used) {
		List<Integer> l = new ArrayList<>();
		for (int i = 0; i < num.length; i++) {
			if (used[i]) {
				l.add(num[i]);
			}
		}
		rs.add(l);
	}

	@Test
	public void tst() {
		int num[] = { 2,3,6,7};
		int target = 7;
		System.out.println(combinationSum2(num, target));
	}
}
